package com.wyw.leetcode.learning.simple;

/**
 * @Title   leetcode topic 700
 * @Description 二叉搜索树中的搜索
 *
 *      给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
 *      你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
 *
 *      二叉查找树（Binary Search Tree），简写BST，是满足某些条件的特殊二叉树。任何一个节点的左子树上的点，都必须小于当前节点。任何一个节点的右子树上的点，都必须大于当前节点。任何一棵子树，也都满足上面两个条件。另外二叉查找树中，是不存在重复节点的。
 *
 * @Author Mr Wu yewen.wu.china@gmail.com
 * Update History:
 * Author        Time            Content
 */
public class Topic700 {

    public static void main(String[] args) {
        TreeNode node = new TreeNode(4);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(7);
        TreeNode node4 = new TreeNode(1);
        TreeNode node5 = new TreeNode(3);

        node.left = node2;
        node.right = node3;

        node2.left=node4;
        node2.right=node5;

        TreeNode treeNode = searchBST(node, 2);
        TreeNode treeNode1 = searchBST2(node, 2);
        System.out.println("end");
    }

    public static TreeNode searchBST(TreeNode root, int val) {
        if(root == null)
            return null;

        if(root.val == val)
            return root;

        TreeNode treeNodeL = searchBST(root.left, val);

        TreeNode treeNodeR = searchBST(root.right, val);

        return treeNodeL == null ? treeNodeR : treeNodeL;
    }

    public static TreeNode searchBST1(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (val == root.val) {
            return root;
        }
        return searchBST1(val < root.val ? root.left : root.right, val);

    }

    public static TreeNode searchBST2(TreeNode root, int val) {

        while(root!=null) {
            if(root.val == val)
                return root;
            else if(root.val > val)
                root = root.left;
            else
                root = root.right;
        }
        return null;
    }


}
